算法概述

线性规划预处理

线性规划

混合整数规划预处理

切割生成

使用启发式方法求出可行解

分支定界

'legacy' intlinprog 算法使用此基本策略来求解混合整数线性规划。intlinprog 可以在任一阶段完成问题的求解。如果它在某个阶段成功求解了问题，intlinprog 不会执行后面的阶段。

使用线性规划预处理缩减问题的规模。

使用线性规划求解初始松弛（非整数）问题。

执行混合整数规划预处理以收紧混合整数问题的 LP 松弛。

尝试切割生成以进一步收紧混合整数问题的 LP 松弛。

尝试使用启发式方法求得整数可行解。

使用分支定界算法系统地搜索最优解。此算法通过限制整数变量的可能值范围来求解 LP 松弛问题。它尝试在最优目标函数值上生成一系列更新边界。

根据混合整数线性规划定义，矩阵 A 和 Aeq 以及对应的向量 b 和 beq 以如下形式编写一组线性不等式和线性等式

A · x≤bAeq · x=beq.

这些线性约束对解 x 施加约束。

通常，我们可以减少问题中的变量数量（x 的分量数量），并减少线性约束的数量。虽然执行这些缩减可能会花费求解器的时间，但它们通常会缩短求解的总时间，并使更大型的问题可求解。这些算法可以使解在数值上更加稳定。此外，这些算法有时可以检测不可行问题。

预处理步骤旨在消除冗余变量和约束，改善模型的尺度和约束矩阵的稀疏性，加强变量的边界，检测模型的原始和对偶不可行性。

有关详细信息，请参阅 Andersen 和 Andersen 的论著 [3] 以及 Mészáros 和 Suhl 的论著 [10]。

初始松弛问题是线性规划问题，其目标和约束与混合整数线性规划定义相同，但没有整数约束。xLP 称为松弛问题的解，x 称为具有整数约束的原始问题的解。显然，

fTxLP ≤ fTx，

因为 xLP 在较少的约束下最小化相同的函数。

此初始松弛 LP（根节点 LP）以及分支定界算法期间生成的所有 LP 松弛都使用线性规划方法来求解。

在混合整数规划预处理期间，intlinprog 分析线性不等式 A*x ≤ b 以及完整性约束，以确定是否有以下情形：

此问题不可行。

有些边界可以收紧，因此有些变量可以固定。

有些不等式是冗余的，因此可以忽略或删除。

一些不等式可以得到加强。

通过 IntegerPreprocess 选项，您可以选择 intlinprog 采取某些步骤、采取所有步骤还是几乎不采取任何步骤。如果包含 x0 参量，intlinprog 会在预处理中使用该值。

混合整数规划预处理的主要目标是简化后续的分支定界计算。预处理包括快速预检查和消除一些无用的子问题候选项，以免分支定界算法对其进行分析。

有关整数预处理的详细信息，请参阅 Achterberg 等人的论著 [1]。

切割是 intlinprog 为问题增加的额外线性不等式约束。这些不等式尝试限制 LP 松弛的可行域，使其解更接近整数。您可以通过 CutGeneration 选项控制 intlinprog 使用的切割类型。

'basic' 切割包括：

混合整数舍入切割

戈莫里切割

Clique 切割

覆盖切割

流覆盖切割

此外，如果问题为纯整数型（所有变量均为整数值），则 intlinprog 还使用以下切割：

强查瓦塔尔-戈莫里切割

零-半切割

'intermediate' 切割包括所有 'basic' 切割，还包括：

简单的提升投影切割

简单的主元缩减切割

缩减拆分切割

'advanced' 切割包括缩减拆分切割以外的所有 'intermediate' 切割，还包括：

强查瓦塔尔-戈莫里切割

零-半切割

对于纯整数型问题，'intermediate' 使用的切割类型最多，因为它使用缩减拆分切割，而 'advanced' 不使用。

另一个选项 CutMaxIterations 指定 intlinprog 迭代切割生成的次数上界。

有关切割生成算法（也称为割平面方法）的详细信息，请参阅 Cornuéjols·的论著 [6]；有关 clique 切割的详细信息，请参阅 Atamtürk、Nemhauser 和 Savelsbergh·的论著 [4]。

为了得到目标函数的上界，分支定界过程必须求得可行点。分支定界过程中，LP 松弛问题的解可能是整数可行的，可用于改进原始 MILP 的上界。某些方法能够在分支定界之前或期间更快地找到可行点。intlinprog 在根节点上以及一些分支定界迭代过程中使用这些方法。这些方法是启发式的，意味着它们是可能成功但也可能失败的算法。

启发式方法可以是初始点启发式方法，它们帮助求解器求得初始或新的整数可行解。启发式方法也可以是改进点启发式方法，它们从整数可行点开始，尝试找到更好的整数可行点，即目标函数值更低的点。intlinprog 改进点启发式方法有 'rins'、'rss'、1-opt、2-opt 和引导潜水。

使用 'Heuristics' 选项设置 intlinprog 使用的启发式方法。选项包括：

求解器使用不同参数运行两次舍入启发式方法，再使用不同参数运行两次潜水启发式方法，然后运行 'rss'。如果前期的启发式方法能得到足够好的整数可行解，则求解器不再运行其后的启发式方法。

求解器使用不同参数运行两次舍入启发式方法，然后使用不同参数运行两次潜水启发式方法。如果有整数可行解，则求解器运行 'rins'，然后运行 'rss'。如果 'rss' 求得新解，求解器将再次运行 'rins'。如果前期的启发式方法能得到足够好的整数可行解，则求解器不再运行其后的启发式方法。

求解器使用不同参数运行两次舍入启发式方法，然后使用不同参数运行两次潜水启发式方法。如果有整数可行解，则求解器运行 'rins'，然后运行 'rss'。如果 'rss' 求得新解，求解器将再次运行 'rins'。如果前期的启发式方法能得到足够好的整数可行解，则求解器不再运行其后的启发式方法。

intlinprog 搜索当前最佳整数可行解点（如有）的邻域，以求得更好的新解。请参阅 Danna、Rothberg 和 Le Pape·的论著 [8]。当您选择 'rins' 时，求解器使用不同参数运行两次舍入启发式方法，再使用不同参数运行两次潜水启发式方法，然后运行 'rins'。

intlinprog 将 'rins' 理念和局部分支理念整合，以混合方式搜索整数可行解。当您选择 'rss' 时，求解器使用不同参数运行两次舍入启发式方法，再使用不同参数运行两次潜水启发式方法，然后运行 'rss'。如果前期的启发式方法能得到足够好的整数可行解，则求解器不再运行其后的启发式方法。这些设置执行与 'basic' 相同的启发式方法。

intlinprog 取节点处松弛问题的 LP 解，并以尝试保持可行性的方式舍入整数分量。当您选择 'round' 时，求解器在根节点上使用不同参数运行两次舍入启发式方法，然后使用不同参数运行两次潜水启发式方法。此后，求解器仅在一些分支定界节点上运行舍入启发式方法。

求解器的工作方式与 'round' 相似，但求解器还在一些分支定界节点上运行潜水启发式方法（在舍入启发式方法的基础上），而不仅限于根节点。

intlinprog 使用类似于分支定界步骤的启发式方法，但只沿树的一个分支向下，而不创建其他分支。此单分支使得算法能够快速下“潜”到树的片段，因此命名为“潜水”。当前，intlinprog 按照以下顺序使用六种潜水启发式方法：

向量长度潜水

系数潜水

小数潜水

伪代价潜水

线搜索潜水

引导式潜水（当求解器已找到至少一个整数可行点时适用）

潜水启发式方法通常选择一个应该取整数值、但当前解为小数的变量。然后，启发式方法引入一个强制变量取整数值的边界，并再次求解相关联的松弛 LP。各种潜水启发式方法之间的主要区别在于如何选择要定界的变量。请参阅 Berthold 的论著·[5]，第 3.1 节。

intlinprog 不搜索可行点。求解器只选取它在分支定界搜索中遇到的任何可行点。

'intermediate' 和 'advanced' 之间的主要区别在于 'advanced' 在分支定界迭代期间更频繁地运行启发式方法。

除了上表之外，当 Heuristics 选项为 'basic'、'intermediate' 或 'advanced' 时，还会运行以下启发式方法。

ZI 取整 - 每当算法解出一个松弛 LP 时，此启发式方法就会运行。该启发式方法遍历每个带小数的整数变量并尝试将其移至邻近的整数，不影响在其他约束下的可行性。有关详细信息，请参阅 Hendel [9]。

1-opt - 每当算法找到新的整数可行解时，此启发式方法就会运行。该启发式方法在降低目标函数值的同时遍历每个整数变量并尝试将其移至邻近的整数，不影响在其他约束下的可行性。

2-opt - 每当算法找到新的整数可行解时，此启发式方法就会运行。2-opt 查找影响同一约束的所有整数变量对组，这意味着它们在 A 或 Aeq 约束矩阵的同一行中有非零项。对于每个对组，2-opt 选取一个整数可行解，并使用所有四个可能的移动（上-上、上-下、下-上和下-下）向上或向下移动变量对组的值，寻找具有更好的目标函数值的可行相邻解。该算法通过计算满足约束的对组中每个变量的最大移位大小（相同幅值）来测试每个整数变量对组，同时改进目标函数值。

在启发式方法阶段开始时，intlinprog 运行平凡启发式方法，除非 Heuristics 是 'none' 或者您在 x0 参量中提供初始整数可行点。平凡启发式方法检查以下各点的可行性：

全部为零

上界

下界（如果非零）

“锁定”点

“锁定”点仅针对所有变量的上界和下界有限的问题定义。每个变量的“锁定”点是其上界或下界，按如下方式进行选择。对于每个变量 j，计算线性约束矩阵 A(:,j) 中对应正条目的数量，并减去对应负条目的数量。如果结果为正值，则使用该变量的下界 lb(j)。否则，使用该变量的上界 ub(j)。“锁定”点尝试满足每个变量的最大数量的线性不等式约束，但不一定可行。

在每个启发式方法都获得一个可行解后，intlinprog 调用输出函数和绘图函数。请参阅intlinprog 输出函数和绘图函数语法。

如果包含 x0 参量，intlinprog 将在 'rins' 中和引导潜水启发式方法中使用该值，直到找到更好的整数可行点。因此，当您提供 x0 时，您可以通过将 'Heuristics' 选项设置为 'rins-diving' 或使用 'rins' 的其他设置来获得满意的结果。

分支定界方法构造一系列尝试收敛到 MILP 解的子问题。子问题给出关于解 fTx 的一系列上界和下界。第一个上界是任何可行解，第一个下界是松弛问题的解。关于上界的讨论，请参阅使用启发式方法求出可行解。

如线性规划中所述，线性规划松弛问题的任何解都比 MILP 解具有更低的目标函数值。此外，任何可行点 xfeas 都满足

fTxfeas ≥ fTx，

因为 fTx 是所有可行点中最小的。

在这种情况下，节点是具有以下特征的 LP：它具有与原始问题相同的目标函数、边界和线性约束，但没有整数约束，并对线性约束或边界作出特定改变。根节点是没有整数约束且线性约束或边界也不发生变化的原始问题，这意味着根节点是初始松弛 LP。

从起始边界开始，分支定界方法通过从根节点产生分支来构造新子问题。分支步骤采用启发式方法，遵循以下规则之一。每个规则都基于这样的理念：约束一个变量，使之小于或等于整数 J，或者大于或等于 J+1，从而拆分问题。当 xLP 中对应于 intcon 所指定整数的项不是整数时，会出现这两个子问题。在此处，xLP 是松弛问题的解。以 J 为变量的下限（向下舍入），以 J+1 为上限（向上舍入）。由此产生的两个问题的解大于或等于 fTxLP，因为这两个问题具有